#!/usr/bin/env python3

"""
Write an efficient algorithm that searches for value in an m x n matrix. This matrix has the following properties:
- Integer in each row are sorted from left to right. 
- The first integer of each row is greater that the last integer of the previous row. 
"""

class Solution:
    def search_matrix(self, matrix, target):
        if len(matrix) == 0 or len(matrix[0]) == 0 \
           or target < matrix[0][0] or target > matrix[-1][-1]:
            return False

        best_lists = self.binary_search(matrix, 0, len(matrix) - 1, target)
        if best_lists is None:
            return False
        if self.binary_search(best_lists, 0, len(best_lists) - 1, target) is not None:
            return True
        return False


    def binary_search(self, items, start_index, end_index, target):
        start = items[start_index]
        end = items[end_index]
        start_compare = self.compare(start, target)
        if start_compare == 0:
            return start
        elif start_compare > 0:
            return None

        end_compare = self.compare(end, target)
        if end_compare == 0:
            return end
        elif end_compare < 0:
            return None
        middle_index = int((start_index + end_index) / 2)
        if middle_index == start_index:
            return None
        middle = items[middle_index]
        middle_compare = self.compare(middle, target)
        if middle_compare == 0:
            return middle
        elif middle_compare > 0:
            return self.binary_search(items, start_index, middle_index, target)
        else:
            return self.binary_search(items, middle_index, end_index, target)

    def compare(self, item, target):
        if type(item) is list:
            first = item[0]
            if first > target:
                return 1
            last = item[-1]
            if last < target:
                return -1
            else:
                return 0
        else:
            return item - target
        
            
if __name__ == '__main__':
    s = Solution()
    true_input = [[-10,-8,-6,-4,-3],[0,2,3,4,5],[8,9,10,10,12]]
    assert s.search_matrix(true_input, 0)
    input = [[1, 3, 5, 7],
             [10, 11, 16, 20],
             [23, 30, 34, 50]]
    assert not s.search_matrix(input, 13)
    assert s.search_matrix(input, 3)
